package 二叉树;

import com.alibaba.fastjson.JSON;
import 链表.ListNode;

import java.util.ArrayDeque;
import java.util.ArrayList;

public class NC8二叉树根节点到叶子节点和为指定值的路径 {

    /**
     * 给定一个二叉树和一个值\ sum sum，请找出所有的根节点到叶子节点的节点值之和等于\ sum sum 的路径，
     * 例如：
     * 给出如下的二叉树，\ sum=22 sum=22，
     *
     * 返回
     * [
     * [5,4,11,2],
     * [5,8,9]
     * ]
     * 示例1
     * 输入
     * 复制
     * {1,2},1
     * 返回值
     * 复制
     * []
     * 示例2
     * 输入
     * 复制
     * {1,2},3
     * 返回值
     * 复制
     * [[1,2]]
     */

    private ArrayList<ArrayList<Integer>> result=new ArrayList<>();
    private int sum;

    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        this.sum=sum;
        if(root!=null) {
            ArrayDeque<Integer> path = new ArrayDeque<>();
            path.addLast(root.val);
            dfs(path, root, root.val);
        }
        return result;
    }

    private void dfs(ArrayDeque<Integer> path,TreeNode node,int target){

        if(node==null){
            return;
        }

        //需要到叶子节点
        if(target==sum&&node.left==null&&node.right==null){
            result.add(new ArrayList<>(path));
        }

        if(node.left!=null) {
            path.addLast(node.left.val);
            dfs(path,node.left,target+node.left.val);
            path.removeLast();
        }
        if(node.right!=null){
            path.addLast(node.right.val);
            dfs(path,node.right,target+node.right.val);
            path.removeLast();
        }

    }

    public static void main(String[] args) {
        NC8二叉树根节点到叶子节点和为指定值的路径 n=new NC8二叉树根节点到叶子节点和为指定值的路径();
        TreeNode root = TreeNode.getNodeByArr(new Integer[]{5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1});
        ArrayList<ArrayList<Integer>> result = n.pathSum(root, 22);
        System.out.println(JSON.toJSONString(result));
    }

}
